package LeetCode.NumOffer;

/**
 * 机器人的运动范围
 * @author lumin
 * @date 2022/04/30 20:16
 **/
public class Num13 {
    public static int movingCount(int m, int n, int k) {
        //标记当前格子是否被访问过
        boolean[][] visited = new boolean[m][n];
        //参数：visited数组、m、n、k、当前所处格子，只往右下走
        return dfs(visited, m, n, k, 0, 0);
    }

    private static int dfs(boolean[][] visited, int m, int n, int k, int i, int j){
        //递归终止条件
        if(i >= m ||  j >= n || isSat(i) + isSat(j) > k || visited[i][j]) return 0;


        visited[i][j] = true;

        //当前格 + 往下走 + 往右走
        return 1 + dfs(visited, m, n, k, i + 1, j) + dfs(visited, m, n, k, i, j + 1);
    }

    private static int isSat(int i) {
        int sum = 0;
        while(i != 0){
            sum += i % 10;
            i = i / 10;
        }
        return sum;
    }

    public static void main(String[] args) {
        int m = 16;
        int n = 8;
        System.out.println(movingCount(m,n,4));
    }

}